package leetcode;

import pojo.TreeNode;

/**
 * 98. 验证二叉搜索树
 *
 * @author yujiafan
 * @version 1.0.0
 * @create 2022-12-29
 */
public class LeetCode98 {

    public static class Info {
        public int min;
        public int max;
        public boolean isBST;

        public Info() {
        }

        public Info(int min, int max, boolean isBST) {
            this.min = min;
            this.max = max;
            this.isBST = isBST;
        }
    }

    public static boolean isValidBST(TreeNode root) {
        if(root == null){
            return false;
        }
        return process(root).isBST;
    }

    public static Info process(TreeNode root){
        int max = root.val;
        int min = root.val;
        boolean isLeft = true;
        boolean isRight = true;
        if(root.left == null && root.right == null){
            return new Info(root.val,root.val,true);
        }
        if(root.left != null){
            Info process = process(root.left);
            isLeft = process.isBST && root.val > process.max;
            min = Math.min(min,process.min);
            max = Math.max(max,process.max);
        }

        if(root.right != null){
            Info process = process(root.right);
            isRight = process.isBST && root.val < process.min;
            min = Math.min(min,process.min);
            max = Math.max(max,process.max);
        }

        boolean isBST = isLeft && isRight;
        return new Info(min,max,isBST);
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(2, new TreeNode(1), new TreeNode(3));
        System.out.println(isValidBST(treeNode));
        TreeNode treeNode1 = new TreeNode(5,new TreeNode(1),new TreeNode(4,new TreeNode(3),new TreeNode(6)));
        System.out.println(isValidBST(treeNode1));

        TreeNode treeNode2 = new TreeNode(1, new TreeNode(1),null);
        System.out.println(isValidBST(treeNode2));

        TreeNode treeNode3 = new TreeNode(5,new TreeNode(4),new TreeNode(6,new TreeNode(3),new TreeNode(7)));
        System.out.println(isValidBST(treeNode3));
    }

}
